/*
Date:220210421 18:32pm
key:我们知道，对于每一个字符，只有融合与独立两个选择。
    那情况就分成三种，只能融合，只能独立，和二者都能。
    只能融合就是dp[i]=dp[i-2],最后一个字符换成2个组合的。
    只能独立就是dp[i]=dp[i-1],最后一个字符换成新的最后字符。
    关键来了，二者都能dp怎么写，不就是dp[i-2]+dp[i-1]吗，利用逻辑，豁然开朗。
*/

class Solution {
public:
    bool test(string&s)
    {
        //如果第一个是0，退出
        if(s[0]=='0')
        {
            return 1;
        }
        
        //0前面只能是1或2，否则退出
        for(int i=1;i<s.size();i++)
        {
            if(s[i]=='0')
            {
                if((s[i-1]!='1')&&s[i-1]!='2'){return 1;}
                
            }
            
        }
        
        return 0;
    }
    int numDecodings(string s) {
        //long long count=0;
        int* dp=new int[s.size()];

        if(test(s))
        {
            return 0;
        }
        for(int i=0;i<s.size();i++)
        {
            if(i==0)
            {
                dp[i]=1;
                continue;
            }
            if(i==1)
            {
                //只能独立
                if(('1'==(s[i-1])&&s[i]>'0'&&s[i]<='9')||('2'==(s[i-1])&&s[i]>'0'&&s[i]<'7'))
                {

                        dp[i]=2;

                }
                else
                {
                    //只能融合
                    if(s[i]=='0')
                    {
                        dp[i]=1;
                    }
                    else
                    {
                        //不存在既不能融合又不能独立的
                        //因此只剩下能融合又能独立的
                        dp[i]=1;
                    }
                    
                }
                    
            }
            
            else
            {
                //只能独立
                if(('1'==(s[i-1])&&s[i]>'0'&&s[i]<='9')||('2'==(s[i-1])&&s[i]>'0'&&s[i]<'7'))
                {

                        dp[i]=dp[i-1]+dp[i-2];

                }
                else
                {
                    //只能融合
                    if(s[i]=='0')
                    {
                        dp[i]=dp[i-2];
                    }
                    else
                    {
                        //不存在既不能融合又不能独立的
                        //因此只剩下能融合又能独立的
                        dp[i]=dp[i-1];
                    }
                    
                }
            }
            
        }

        return dp[s.size()-1];
        
    }
};